package com.backpack;

import java.util.Arrays;

public class HouseRobberII0114_213 {
    public int rob(int[] nums) {
        //将环形数组拆解为两个线性数组：包含头元素不含尾元素、 不含头元素含有尾元素

        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];

        //包含头元素不含尾元素
        int[] numsHead = new int[nums.length-1];
        System.arraycopy(nums, 0, numsHead, 0, nums.length - 1);

        //包含头元素不含尾元素
        int[] numsTail = new int[nums.length-1];
        System.arraycopy(nums, 1, numsTail, 0, nums.length - 1);

        return Math.max(houseRobber(numsHead),houseRobber(numsTail));
    }

    private int houseRobber(int[] nums) {
        // 同打家劫舍I 题目一样
        if(nums.length == 1) return nums[0];

        //动态规划
        //dp[i] 表示 考虑下标 i（含） 能够偷得到的最大价值为dp[i]       返回值 dp[nums.length-1]
        int[] dp = new int[nums.length];

        //初始化
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        // 第 i 家 只有两种情况 偷（i-1 不偷） 与 不偷（i-2）
        //递归公式：dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}
